import jdk.nashorn.internal.ir.IfNode;

public class JZ53_1 {
    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     *
     * 统计一个数字在排序数组中出现的次数。
     * 示例 1:
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     */
        public int search(int[] nums, int target) {
            // 搜索右边界 right
            int i = 0, j = nums.length - 1;

            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] <= target) {
                    i = m + 1;
                } else {
                    j = m - 1;
                }
            }

            int right = i;
            // 若数组中无 target ，则提前返回
            if(j >= 0 && nums[j] != target) {
                return 0;
            }
            // 搜索左边界 right
            i = 0; j = nums.length - 1;

            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] < target) {
                    i = m + 1;
                } else {
                    j = m - 1;
                }
            }
            int left = j;
            return right - left - 1;
        }

}